#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include "Cluster.h"
#define OK 1
#define TRUE 1
#define FALSE 0
//定义读写比例值的
int Cw_temp=9;
int Cr_temp=1;
int MAX_Cluster=8;
//簇的最大大小

//函数实体定义
void InitCLRUList(BufList *CHead)
{
    *CHead=(BufList)malloc(sizeof(BufNode));
    if(*CHead==NULL)
    {
        printf("CLRU链表初始化失败\n");
        getchar();
        exit(0);
    }else
    {
        //L就是虚拟表头
        (*CHead)->next=(*CHead)->pre=*CHead;
    }
}

void InitDLRUList(BufList *DHead)
{
    *DHead=(BufList)malloc(sizeof(BufNode));
    if(*DHead==NULL)
    {
        printf("DLRU双链表初始化失败\n");
        getchar();
        exit(0);
    }else
    {
        //DHEAD就是虚拟表头
        (*DHead)->next=(*DHead)->pre=*DHead;
    }
}

void InitLVBNList(LVBNList *LHead)
{
    *LHead=(LVBNList)malloc(sizeof(LVBNNode));
    if(*LHead==NULL)
    {
        printf("DLRU双链表初始化失败\n");
        getchar();
        exit(0);
    }else
    {
        //Head就是虚拟表头
        (*LHead)->next=*LHead;
        (*LHead)->pre=*LHead;
        if((*LHead)->pre==NULL)
        {
          printf("LHead->pre exist error\n");
          exit(0);
        }
    }
}

Status DestroyCLRUList(BufList *CHead)
{
/* 操作结果：销毁双向循环链表L */
   BufList q,p=(*CHead)->next; /* p指向第一个结点 */
   while(p!=*CHead) /* p没到表头 */
   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*CHead);
   *CHead=NULL;
   return OK;
}

Status DestroyDLRUList(BufList *DHead)
{
/* 操作结果：销毁双向循环链表L */
    BufList q,p=(*DHead)->next; /* p指向第一个结点 */
   while(p!=*DHead) /* p没到表头 */
   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*DHead);
   *DHead=NULL;
   return OK;
}

BufList FindLPNinCLRU(BufList CHead,ElemeType LPN)
{
     /*从CLRU双链表中寻找是否存在该LPN号的页，存在则返回该页的位置指针
     若不存在，返回的地址是NULL*/
     BufList r,p;
     r=NULL;
     p=CHead->next;
     while(p!=CHead)
     {
         if(p->LPN==LPN)
         {
             /*表示存在该LPN号*/
             r=p;//将该数据页的地址返回
             return r;
         }
         p=p->next;
     }
     return r;//此时返回的r是NULL
}

BufList FindLPNinDLRU(BufList DHead,ElemeType LPN)
{
     /*从DLRU双链表中寻找是否存在该LPN号的页，存在则返回该页的位置指针
     若不存在，返回的地址是NULL*/
     BufList r,p;
     r=NULL;
     p=DHead->next;
     while(p!=DHead)
     {
         if(p->LPN==LPN)
         {
             /*表示存在该LPN号*/
             r=p;//将该数据页的地址返回
             return r;
         }
         p=p->next;
     }
     return r;//此时返回的r是NULL
}

Status CLRULength(BufList CHead)
{
/* 初始条件：CHead已存在。操作结果：返回CHead中数据元素个数 */
   int i=0;
   BufList p=CHead->next; /* p指向第一个结点 */
   while(p!=CHead) /* p没到表头 */
   {
     i++;
     p=p->next;
   }
   return i;
}

Status DLRULength(BufList DHead)
{
/* 初始条件：DHead已存在。操作结果：返回DHead中数据元素个数 */
   int i=0;
   BufList p=DHead->next; /* p指向第一个结点 */
   while(p!=DHead) /* p没到表头 */
   {
     i++;
     p=p->next;
   }
   return i;
}

Status AddNewToCLRU(BufList CHead,ElemeType LPN,int flag)
{
    //参数说明1LPN,2操作类型，一般写操作为0
    BufList temp=NULL;
    temp=(BufList)malloc(sizeof(BufNode));
    if(temp==NULL)
    {
        fprintf(stderr,"AddNewToCLRU节点分配内存错误\n");
        getchar();
        exit(0);
    }
    temp->isD=flag;
    temp->LPN=LPN;
    //将节点嵌入到MRU位置
    CHead->next->pre=temp;
    temp->next=CHead->next;
    temp->pre=CHead;
    CHead->next=temp;
    return OK;
}

Status AddNewToDLRU(BufList DHead,ElemeType LPN,int flag)
{
    //参数说明1LPN,2操作类型，一般写操作为0
    BufList temp=NULL;
    temp=(BufList)malloc(sizeof(BufNode));
    if(temp==NULL)
    {
        fprintf(stderr,"节点分配内存错误\n");
        getchar();
        exit(0);
    }
    temp->isD=flag;
    temp->LPN=LPN;
    //将节点嵌入到MRU位置
    DHead->next->pre=temp;
    temp->next=DHead->next;
    temp->pre=DHead;
    DHead->next=temp;
    return OK;
}


Status DeleteCLRUend(BufList CHead)
{
    //剔除操作是脏页的时候，返回的是0.非脏页为非零值
    //实际CLRU剔除的都是干净页
    BufList p,q;
    p=CHead->pre;
    q=p->pre;
    int flag=p->isD;
    q->next=CHead;
    CHead->pre=q;
    //释放LRU位置的数据
    free(p);
    return flag;
}

Status DeleteDLRUend(BufList DHead)
{
    //剔除操作是脏页的时候，返回的是0.非脏页为非零值
    BufList p,q;
    p=DHead->pre;
    q=p->pre;
    int flag=p->isD;
    q->next=DHead;
    DHead->pre=q;
    //释放LRU位置的数据
    free(p);
    return flag;
}
//该函数实现将CLRU中命中的节点转移置DLRU节点的MRU位置,
Status MoveCLRUtoDLRU(BufList DHead,BufList HitLPN)
{
    BufList temp;
    temp=HitLPN->pre;
    //先从CLRU的链表中删除该命中节点
    temp->next=HitLPN->next;
    HitLPN->next->pre=temp;
    //将该节点插入到DLRU的MRU位置
    DHead->next->pre=HitLPN;
    HitLPN->next=DHead->next;
    DHead->next=HitLPN;
    HitLPN->pre=DHead;
    return OK;
}

int ComputeTau(BufList DHead,BufList CHead,int *tau,int flag)
{
    int DL=DLRULength(DHead);
    int CL=CLRULength(CHead);
    //根据读写代价归一化占比
    double Cr=(double)Cr_temp/(Cr_temp+Cw_temp);
    double Cw=(double)Cw_temp/(Cr_temp+Cw_temp);
    //t是*tau的增加值或者减小值,tp是为了实现计算四舍五入的中间值
    double tp=0.0;
    int t=0;
    //根据命中的区域来区别操作
    //flag=0,命中DLRU（减小tau）
    //flag!=0,命中CLRU（增加tau）
    if(flag)
    {
        //命中CLRU，增加tau
        tp=((double)DL/CL)*Cr;
        //对增加值进行四舍五入计算
        t=(int)(tp+0.5)>(int)tp?(int)tp+1:(int)tp;
        *tau=*tau+t;
    }else
    {
        //命中DLRU,减小tau
        tp=((double)CL/DL)*Cw;
        //对增加值进行四舍五入计算
        t=(int)(tp+0.5)>(int)tp?(int)tp+1:(int)tp;
        *tau=*tau-t;
        //防止出现tau值为负
        if(*tau<0)
        {
            *tau=0;
        }
    }
    //返回值为更改后的tau值
    return OK;
}
/***************************************************/
/***************************************************/
//添加的新代码cluster

Status DestroyLVBNList(LVBNList *Head)
{
    LVBNList p=(*Head)->next,q;
    while(p!=*Head)
    {
        q=p;
        p=p->next;
        free(q);
    }
    free(*Head);
    *Head=NULL;
    return OK;
}

int LVBNListLength(LVBNList Head)
{
/* 初始条件：Head已存在。操作结果：返回Head中数据元素个数 */
   int i=0;
   LVBNList p=Head->next; /* p指向第一个结点 */
   while(p!=Head) /* p没到表头 */
   {
     i++;
     p=p->next;
   }
   return i;
}

int LPNtoLVBN(ElemeType LPN)
{
/*该函数完成对LPN转换为簇号,返回的是簇号*/
    int LVBN,offset;
    offset=(int)LPN%MAX_Cluster;
    LVBN=(int)LPN/MAX_Cluster;
    //如果LVBN的索引从1开始
    if(offset==0)
    {
        offset=MAX_Cluster;
    }else
    {
        LVBN++;
    }
    return LVBN;
}

//该函数返回的是指向该LVBN节点的指针,如果不存在则返回NULL
LVBNList FindLVBNinList(LVBNList Head,ElemeType LVBN)
{
      LVBNList q=NULL;
      q=Head->next;
      int count=0;
      while(q!=Head)
      {
           q->LPNStart=count;
          if(q->LVBN==LVBN)
          {
              return q;
          }
           count+=q->cluster_size;
          q=q->next;
      }
        return NULL;
}

//更新所有的LVBNList中的开始位置
void UpdateStartLVBNList(LVBNList Head)
{
    LVBNList q=Head->next;
    int count=0;
    while(q!=Head)
    {
        q->LPNStart=count;
        count+=q->cluster_size;
        q=q->next;
    }
}

//删除LVBNList的LRU位置节点,返回删除簇的大小
int DeleteLVBNend(LVBNList Head)
{

    LVBNList temp=Head->pre;
    int DelSize=temp->cluster_size;
    temp->pre->next=Head;
    Head->pre=temp->pre;
    free(temp);
    return DelSize;
}

//增加新的LVBN到列表中，这种情况下的LPN也是不存在DLRU中的
//该函数在结束时调用了一次UpdateStartLVBNlist函数
Status AddNewToLVBN(LVBNList Head,ElemeType LVBN)
{
    LVBNList temp=NULL;
    temp=(LVBNList)malloc(sizeof(LVBNNode));
    if(temp==NULL)
    {
        fprintf(stderr,"LVBNList节点分配内存错误\n");
        getchar();
        exit(0);
    }
    //新簇的大小是1，起始位置是0；
    temp->cluster_size=1;
    temp->LVBN=LVBN;
    temp->LPNStart=0;
    //将新节点加入到链表的头部
    temp->next=Head->next;
    temp->pre=Head;
    //
    Head->next->pre=temp;
    Head->next=temp;
    //嵌入新节点之后，更新所有的节点的相对起始位置
    UpdateStartLVBNList(Head);
    return OK;
}

//将命中的LVBN移动到MRU位置，命中有两种
/**************************
hit_type
* 0:LVBN存在，同时LPN也在DLRU中
* 1:LVBN存在，但LPN不存在DLRU中
**************************/
Status LVBNMovetoMRU(LVBNList Head,LVBNList HitLVBN,int hit_type)
{
    if(hit_type)
    {
        HitLVBN->cluster_size++;
    }
    LVBNList temp=HitLVBN->pre;
    //从原来位置断开连接
    temp->next=HitLVBN->next;
    HitLVBN->next->pre=temp;
    //将节点插入到头部
    HitLVBN->next=Head->next;
    HitLVBN->pre=Head;
    Head->next->pre=HitLVBN;
    Head->next=HitLVBN;
    //更新所有节点的相对起始位置
    UpdateStartLVBNList(Head);
    return OK;
}

//删除DLRU中LRU的簇,在调用DeleteLVBNend()之前调用处理DLRU
//返回删除的项目数，以便记录回写次数
Status DeleteDLRUendCluster(BufList DHead,LVBNList Head)
{
    LVBNList tail=Head->pre;
    int DelSize=tail->cluster_size,index;
    BufList StNode;
    StNode=DHead->pre;
    //从DLRU的链表尾部开始定位StNode
    index=1;
    while(index<DelSize)
    {
            StNode=StNode->pre;
            index++;
    }
    //完成St的定位，开始逐段删除
    while(StNode!=DHead)
    {
        BufList temp;
        temp=StNode;
        //StNode移位
        StNode=StNode->next;
        //切断temp连接
        temp->pre->next=StNode;
        StNode->pre=temp->pre;
        //释放temp节点
        free(temp);
    }
    return DelSize;
}


//定义函数，可以返回链表中第i个元素的地址指针,从0开始计数
BufList LocateIndexDLRU(BufList DHead,int I)
{
    BufList temp=DHead->next;
    int index=0;
    //错误处理如果索引I超出了链表的大小，报错
    if(I>DLRULength(DHead))
    {
        fprintf(stderr,"索引超出了当前DLRU的长度\n");
        exit(0);
    }
    while(index<I)
    {
        temp=temp->next;
        index++;
    }
    return temp;
}
//将DLRU命中的整个簇移动到MRU位置
//函数调用顺序
/***************************************************************************
    HitLVBN______Hit LPN in DLRU->MoveClusterToMRU->LVBNMovetoMRU(hit_type=0)
            |
            |
            |
            |____No Hit LPN in DLRU->MoveClusterToMRU
                |__AddNewToDLRU
                  |___->LVBNMovetoMRU(hit_type=1)
*****************************************************************************/
Status MoveClusterToMRU(BufList DHead,LVBNList HitLVBN)
{
    int index=HitLVBN->LPNStart;
    int size=HitLVBN->cluster_size;
    //索引是从0开始计数，对应LVBN中的LPNStart也是从0开始
    BufList St=LocateIndexDLRU(DHead,index);
    BufList Et=LocateIndexDLRU(DHead,index+size-1);
    //实现将St--->Et之间的节点切断
    BufList temp1=St->pre,temp2=Et->next;
    temp1->next=temp2;
    temp2->pre=temp1;
    //将St------->Et之间的节点接入MRU位置
    St->pre=DHead;
    Et->next=DHead->next;
    DHead->next->pre=Et;
    DHead->next=St;
    return OK;
}

Status MoveToMRU(BufList L,BufList HitLPN)
{
    //先切断
    BufList temp=HitLPN->pre;
    HitLPN->next->pre=temp;
    temp->next=HitLPN->next;
    //插入MRU位置
    HitLPN->pre=L;
    HitLPN->next=L->next;
    L->next->pre=HitLPN;
    L->next=HitLPN;
    return OK;
}


BufList QuickSearchDLRU(BufList DHead,LVBNList HitLVBN,ElemeType LPN)
{
    int index=HitLVBN->LPNStart;
    int size=HitLVBN->cluster_size;
    //索引是从0开始计数，对应LVBN中的LPNStart也是从0开始
    BufList St=LocateIndexDLRU(DHead,index);
    BufList Et=LocateIndexDLRU(DHead,index+size-1);
    while(St!=Et->next)
    {
        //如果找到对应的LPN则返回
        if(St->LPN==LPN)
        {
            return St;
        }
        St=St->next;
    }
    return NULL;
}
